// m

// 给定一个整数数组nums，数组中的元素互不相同
// 返回该数组所有可能的不重复子集

// 解题思路1： 回溯算法
// 数组中的每个元素都有两个选择，选或者不选
// 1. 定义回溯函数，backtracking(nums, index),nums，可选数组列表，index，正在考虑的元素，全局变量res，存放符合条件结果的集合数组
// path，符合条件的结果
// 在选择nums[index]的情况下，递归选择剩下的元素

// 2. 书写回溯函数主体
//      1. 约束条件，之前选过的不再重复选择，每次从index位置开始遍历，而不是从0位置，避免重复
//      2. 选择元素：将其添加到当前子集数组path中
//      3. 递归搜索：在选择该元素的情况下，继续递归考虑下一个位置上的元素
//      4. 撤销选择：将该元素从当前子集数组path中移除

function subsets(nums) {
    let res = []  // 存放所有符合条件结果的集合
    let path = [] // 存放当前符合条件的结果
    function backtracking(nums, index) { // 正在考虑可选列表中第index个元素
        res.push(path.slice(0)) // 将当前符合条件的结果放入集合中
        if (index >= nums.length) {
            return
        }
        for (let i = index; i < nums.length; i++) {
            path.push(nums[i]) // 选择元素
            backtracking(nums, i + 1) // 递归搜索
            path.pop() // 撤销选择
        }
    }
    backtracking(nums, 0)
    return res
}

let nums = [1, 2, 3]
console.log(subsets(nums))


// 解题思路2： 二进制枚举
// 对于每个元素有两种状态，选取和未选取，我们用1表示选取，0表示不选取
// 我们可以用一个长度为n的二进制数来表示集合nums或者nums的子集
// 对于长度为n的集合，需要枚举0-2^n-1,可以得到所有子集
function subsets2(nums) {
    let n = nums.length
    let sub_sets = []
    for (let i = 0; i < 1 << n; i++) {
        let sub_set = []
        for (let j = 0; j < n; j++) {
            if (i >> j & 1) { // 如果第i位元素对应二进制位1，则表示选取该元素
                sub_set.push(nums[j]) // 将选取的元素加入到子集sub_set
            }            
        }
        sub_sets.push(sub_set)
    }
    return sub_sets
}
console.log(subsets2(nums))